package codingforgreat.lchot150;

import java.util.ArrayList;
import java.util.List;

public class Lc212 {
    public class TireNode{
        int pass;
        boolean end;
        TireNode[] nexts;
        String word;
        public TireNode(){
            pass = 0;
            end = false;
            nexts = new TireNode[26];
            word = null;
        }
    }
    public List<String> findWords(char[][] board, String[] words) {
        TireNode root = new TireNode();
        TireNode cur = root;
        for(String s : words){
            char[] str = s.toCharArray();
            cur = root;
            cur.pass++;
            for(char ch : str){
                int next = ch - 'a';
                if(cur.nexts[next] == null){
                    cur.nexts[next] = new TireNode();
                }
                cur = cur.nexts[next];
                cur.pass++;
            }
            cur.end = true;
            cur.word = s;
        }

        List<String> ans = new ArrayList<String>();
        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){
                process(board,i,j,ans,root);
            }
        }
        return ans;
    }
    public int process(char[][] board,int row,int col,List<String> ans,TireNode cur){
        char cha = board[row][col];
        if(cha == 0){
            return 0;
        }
        int index = cha - 'a';
        if(cur.nexts[index] == null || cur.nexts[index].pass == 0){
            return 0;
        }
        cur = cur.nexts[index];
        int fix = 0;
        if(cur.end){
            ans.add(cur.word);
            cur.end = false;
            fix++;
        }
        board[row][col] = 0;
        if (row > 0) {
            fix += process(board, row - 1, col,ans,cur);
        }
        if (row < board.length - 1) {
            fix += process(board, row + 1, col,ans,cur);
        }
        if (col > 0) {
            fix += process(board, row, col - 1,ans,cur);
        }
        if (col < board[0].length - 1) {
            fix += process(board, row, col + 1,ans,cur);
        }
        board[row][col] = cha;
        cur.pass -= fix;
        return fix;
    }
}
